//
// Created by Snow on 2023/3/4.
//
#include<cstdlib>
#include<cstdio>
typedef int ElemType;
typedef struct DNode
{
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
}DLinkNode;
//头插法建立双链表
bool CreatListF(DLinkNode *&L,ElemType arr[],int n)//由含n个元素的数组arr创建带头结点的双链表L
{
    DLinkNode *s;
    L=(DLinkNode *)malloc(sizeof(DLinkNode));//创建头结点
    L->prior=L->next=NULL;//前后指针域置为NULL
    for(int i=0;i<n;i++)//循环建立数据结点
    {
        s=(DLinkNode *)malloc(sizeof(DLinkNode));
        s->data=arr[i];//创建数据结点s
        s->next=L->next;//将s结点插入头结点之后
        if(L->next!=NULL)//若L非空，修改L->next的前驱指针
            L->next->prior=s;
        L->next=s;
        s->prior=L;
    }
    return true;
}
//尾插法建立双链表
bool CreatListR(DLinkNode *&L,ElemType arr[],int n)
{
    DLinkNode *s,*r;
    L=(DLinkNode *)malloc(sizeof(DLinkNode));
    r=L;
    for(int i=0;i<n;i++)
    {
        s=(DLinkNode *)malloc(sizeof(DLinkNode));
        s->data=arr[i];
        r->next=s;
        s->prior=r;
        r=s;
    }
    r->next=NULL;
    return true;
}
bool ListInsert(DLinkNode *&L,int i,ElemType e)
{
    int j=0;
    DLinkNode *p=L,*s;
    if(i<=0)return false;
    while(j<i-1&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)return false;
    else
    {
        s=(DLinkNode *)malloc(sizeof(DLinkNode));
        s->data=e;
        s->next=p->next;
        if(p->next!=NULL)
            p->next->prior=s;
        s->prior=p;
        p->next=s;
        return true;
    }
}
bool ListDelete(DLinkNode *&L,int i,ElemType &e)
{
    int j=0;
    DLinkNode *p=L,*q;
    if(i<=0)return false;
    while(j<i-1&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    else
    {
        q=p->next;
        if(q==NULL)return false;
        e=q->data;
        p->next=q->next;
        if(q->next!=NULL)
            q->next->prior=p;
        free(q);
        return true;
    }
}
bool DispList(DLinkNode *L)
{
    if(L==NULL)return false;
    DLinkNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return true;
}
bool DestroyList(DLinkNode *&L)
{
    DLinkNode *pre=L,*p=L->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=p->next;
    }
    free(pre);
    return true;
}
void reverse(DLinkNode *&L)
{
    DLinkNode *p=L->next,*q;
    L->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        p->next=L->next;
        if(L->next!=NULL)
            L->next->prior=p;
        L->next=p;
        p->prior=L;
        p=q;
    }
}
void sort(DLinkNode *&L)
{
    DLinkNode *p,*pre,*q;
    p=L->next->next;
    L->next->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        pre=L;
        while(pre->next!=NULL&&pre->next->data<p->data)
        {
            pre=pre->next;
        }
        p->next=pre->next;
        if(pre->next!=NULL)
        {
            pre->next->prior=p;
        }
        pre->next=p;
        p->prior=pre;
        p=q;
    }
}
int main()
{
    ElemType e,arr[]={1,2,3,4,5,6};
    DLinkNode *L;
    CreatListR(L,arr,6);
    DispList(L);
    reverse(L);
    DispList(L);
    DestroyList(L);
    CreatListF(L,arr,6);
    DispList(L);
    ListInsert(L,3,3);
    ListDelete(L,4,e);
    sort(L);
    DispList(L);
    DestroyList(L);
}